package oj.oj_面试题17;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    static class IntegerReverseComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            // return o2 - o1;

            // 咱保证优先级队列中不会出现 null
            // 可以断言 o1 != null && o2 != null
            int i1 = o1;
            int i2 = o2;

            // return i1 - i2; // 正常的顺序
            // i1 是 5    i2 = 3
            // i2 - i3 是一个负数
            // 负数代表：i1 小于 i2
            // 咱们想做到的: 5 “小于” 3
            return i2 - i1; // 相反的顺序
        }
    }

    public int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }

        // 要找到最小的 K 个数，所以要建一个最大容量是 K 的大堆
        // java.util.ProrityQueue 内部实现是小堆
        // 我们重新定义 int 类型的大小关系即可
        // 定义 5 “小于” 3；3 “大于” 5；3 等于 3
        // “小堆” 找出最小的数（实际就是我们平时理解的最大的数）
        // Integer 有一个自然顺序 Comparable（不符合我们的要求）
        // 使用一个 Comparator 去实现
        // 咱保证优先级队列中不会出现 null
        // 使用 PriorityQueue 来当堆使用

        Comparator<Integer> c = new IntegerReverseComparator();
        // 传入 Comparator 构建优先级队列
        PriorityQueue<Integer> queue = new PriorityQueue<>(c);

        // 把前 k 个数放入堆中
        for (int i = 0; i < k; i++) {
            queue.offer(arr[i]);
        }

        // 拿着剩下的元素和堆顶元素比较
        for (int i = k; i < arr.length; i++) {
            int e = arr[i];
            int t = queue.peek();

            // 比我们堆顶元素小的（我们平时理解的小），才有资格当候选
            if (e < t) {
                // 先把堆顶元素删除（前 K 个里肯定没有它的份了）
                queue.poll();
                // 把新的候选人放入堆中
            }
        }

        // 整个过程完成之后，优先级队列中保存的就是我们的 Top-K（最小的 K 个数）
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = queue.poll();
        }

        // 以任意顺序返回这k个数均可。
        return ans;
    }
}
